package LeetCode.exercise;

public class Main {
    public static void main(String[] args) {
        int[] a = {5,6,3,10,7,5};
        int m = 4;
        int res = function(a, m);
        System.out.println(res);
    }
    public static int function(int[] a, int m) {
        int max = a[a.length-1];
        int sum = a[a.length-1];
        for (int i = 0; i < a.length - 1; i++) {
            if(a[i] > max){
                max = a[i];
            }
            sum += a[i];
        }
        int left = max, right = sum;
        while(left < right){
            int mid = (left + right) / 2;
            int count = 0, tmp = mid;
            for (int i = 0; i < a.length;) {
                while (true) {
                    if(i < a.length && tmp - a[i] >= 0){
                        tmp -= a[i++];
                    } else {
                        tmp = mid;
                        count++;
                        break;
                    }
                }
            }
            if(count <= m){
                right = mid;
            } else {
                left = mid + 1;
            }

        }
        return left;
    }
}
